#pragma once
#include"Common.h"

//将内存页 ID（PAGE_ID）高效映射到管理该页的 Span 结构指针

//1. Single-level array
template<int BITS>
//单级数组映射（适合小地址空间）,本质是一个直接索引的数组
class TCMalloc_PageMap1
{
private:
	static const int LENGTH = 1 << BITS;//数组长度为2^BITS
	void** array_;//存储映射关系的数组（PAGE_ID → Span*）

public:
	typedef uintptr_t Number; // PAGE_ID 类型（无符号整数）

	// 构造函数：分配并初始化数组
	explicit TCMalloc_PageMa1()
	{
		//总大小：每个元素是指针（8字节），共2^BITS个
		size_t size = sizeof(void*) << BITS;
		//按页大小对齐
		size_t alignSize = SizeClass::_RoundUp(size, 1<<PAGE_SHIFT);
		// 分配对齐后的内存（页数=alignSize/页大小）
		array_ = (void**)SystemAlloc(alignSize >> PAGE_SHIFT);
		memset(array_, 0, sizeof(void*) << BITS);  // 初始化为NULL
	}

	// 根据PAGE_ID获取对应的Span*（不存在返回NULL）
    void* get(Number k) const {
        if ((k >> BITS) > 0) {  // 检查k是否超出范围（k的高位是否超过BITS）
            return NULL;
        }
        return array_[k];  // 直接数组访问（O(1)）
    }

    // 设置PAGE_ID对应的Span*（需确保k在范围内）
    void set(Number k, void* v) {
        array_[k] = v;  // 直接赋值（O(1)）
    }

};

//2.二级基数树
//当BITS较大（如 20~30）时，单级数组内存占用过高。
//二级基数树将BITS分解为两级索引，降低单个数组的大小，适合中等地址空间

//用根节点（一级索引） 管理 32 个叶子节点指针；
//用叶子节点（二级索引） 存储具体的 “页 ID→Span*” 映射；
//通过位运算拆分页 ID 为两级索引，实现高效查询和内存按需分配。
template<int BITS>
class TCMalloc_PAgeMap2
{
private:
	// 一级索引（根节点）：5位，共32个条目（2^5=32）
	static const int ROOT_BITS = 2;
	static const int ROOT_LENGTH = 1 << ROOT_BITS;

	// 二级索引（叶子节点）：剩余位数 = BITS - 5
    static const int LEAF_BITS = BITS - ROOT_BITS;
    static const int LEAF_LENGTH = 1 << LEAF_BITS;

	// 叶子节点结构：存储LEAF_LENGTH个映射（Span*）
	struc Leaf {
		void* value[LEAF_LENGTH];
	}

	// 根节点：指向32个叶子节点的指针数组
	Leaf* root_[ROOT_LLENGTH];

public:
	typedef uintptr_t Number; // PAGE_ID 类型（无符号整数）

	// 构造函数：初始化根节点，并预分配内存
    explicit TCMalloc_PageMap2() {
        memset(root_, 0, sizeof(root_));  // 根节点初始化为NULL
        PreallocateMoreMemory();  // 预分配所有可能的叶子节点
    }

	// 根据PAGE_ID获取Span*
    void* get(Number k) const {
        const Number i1 = k >> LEAF_BITS;  // 一级索引（高LEAF_BITS位）
        const Number i2 = k & (LEAF_LENGTH - 1);  // 二级索引（低LEAF_BITS位）
        // 检查k是否超出范围，或叶子节点未分配
        if ((k >> BITS) > 0 || root_[i1] == NULL) {
            return NULL;
        }
        return root_[i1]->values[i2];  // 两级索引访问（O(1)）
    }

	// 设置PAGE_ID对应的Span*
    void set(Number k, void* v) {
        const Number i1 = k >> LEAF_BITS;  // 一级索引
        const Number i2 = k & (LEAF_LENGTH - 1);  // 二级索引
        ASSERT(i1 < ROOT_LENGTH);  // 确保索引有效
        root_[i1]->values[i2] = v;  // 两级索引赋值
    }

	// 确保[start, start+n-1]范围内的PAGE_ID都有对应的叶子节点（避免访问空指针）
	bool Ensure(Number start, size_t n) {
		for(Number key = start; key < start + n - 1; key++) {
			const Number i1 = key >> LEAF_BITS;  // 一级索引
			if(i1 >= ROOT_LENGTH) return false;  // 超出范围

			// 若叶子节点未分配，则创建（使用对象池提高效率）
			if(root_[i1] == NULL) {
				static ObjectPool<Leaf> leafPool;  // 叶子节点对象池
				Leaf* leaf = (Leaf*)leafPool.New();  // 从对象池获取空闲对象
				memset(leaf, 0, sizeof(*leaf));//初始化
				root_[i1] = leaf;
			}

			// 跳过当前叶子节点覆盖的所有key（批量处理）
			// 例如：若LEAF_BITS=5，则跳过0~31，0~63，0~127，...
            key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
		}
		return true;
	}

	// 预分配所有可能的叶子节点（覆盖2^BITS个PAGE_ID）
    void PreallocateMoreMemory() {
        Ensure(0, 1 << BITS);
    }
};
	
//3. 三级基数树（适合大地址空间）
template<int BITS>
class TCMalloc_PageMap3 {
private:
	// 前两级内部节点的位数：(BITS+2)/3（向上取整）
	static const int INTERIOR_BITS = (BITS + 2) / 3;
	// 前两级内部节点的数量：2^INTERIOR_BITS
	static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS;

	// 三级索引（叶子节点）：剩余位数 = 位数 - 前两级内部节点位数之和
	static const int LEAF_BITS = BITS - INTERIOR_BITS;
	// 叶子节点的条目数（2^LEAF_BITS）
    static const int LEAF_LENGTH = 1 << LEAF_BITS;

	// 内部节点（前两级）：存储指向子节点的指针数组
	struct Node {
		Node* ptrs[INTERIOR_LENGTH]
	};

	// 叶子节点（第三级）：存储实际的映射值（键→值）
	struct Leaf {
		void* values[LEAF_LENGTH];
	};

	Node* root_;  // 根节点（一级内部节点）
	//函数指针，用于分配内存（用于创建内部节点）
    void* (*allocator_)(size_t);

	//用函数指针 allocator_ 来分配内存
	//(*allocator_) 表示调用函数指针指向的内存分配函数
	//sizeof(Node) 计算 Node 类型所需的内存大小
	//reinterpret_cast<Node*> 将分配函数返回的 void* 指针转换为 Node* 类型
	Node* NewNode() {
		//Node* node = (Node*)allocator_(sizeof(Node));//C,完全可以
		Node* result = reinterpret_cast<Node*>(allocator_(sizeof(Node)));//C++更安全
		if(result != NULL)
		{
			memset(result, 0, sizeof(*node));
		}
		return result;
	}

public:
	typedef uintptr_t Number;

	explicit TCMalloc_PageMap3(void* (*allocator)(size_t)) {
    	allocator_ = allocator;  // 保存内存分配函数（由外部提供）
    	root_ = NewNode();       // 创建根节点（一级内部节点）
	}

	//2. get方法：根据页号查询映射值（以BITS=20为例）
	//i1：取 k 的最高 7 位（跳过中间 7 位和最低 6 位）。
	//i2：取 k 的中间 7 位（跳过最低 6 位后，用INTERIOR_LENGTH-1掩码提取 7 位）。
	//i3：取 k 的最低 6 位（用LEAF_LENGTH-1掩码提取 6 位）。
	void* get(Number k) const {
		// 分解页号k为三级索引（i1：一级索引，i2：二级索引，i3：三级索引）
		const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);  // 最高位：跳过叶子和二级的位数
		const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1);  // 中间位：掩码取二级位数
		const Number i3 = k & (LEAF_LENGTH - 1);  // 最低位：掩码取叶子位数

		// 检查边界：k是否超出BITS范围，或节点未分配
		if ((k >> BITS) > 0 || root_->ptrs[i1] == NULL || root_->ptrs[i1]->ptrs[i2] == NULL) {
			return NULL;
		}

		// 三级索引访问：root → i1节点 → i2节点（叶子）→ i3位置
		return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3];
	}

	//3. set方法：设置页号对应的映射值
	void set(Number k, void* v) {
		assert(k >> BITS == 0);  // 确保k在BITS范围内（否则断言失败）
		const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
		const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1);
		const Number i3 = k & (LEAF_LENGTH - 1);

		// 直接设置叶子节点中i3位置的值（假设节点已通过Ensure创建）
		reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v;
	}

	//4. Ensure方法：预分配节点（避免空指针访问）
	bool Ensure(Number start, size_t n) {
		for (Number key = start; key <= start + n - 1;) {  // 遍历需要覆盖的key范围
			// 分解当前key的一级和二级索引（叶子节点由i2指向）
			const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS);
			const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH - 1);

			if (i1 >= INTERIOR_LENGTH || i2 >= INTERIOR_LENGTH)
				return false;  // 索引超出范围（无效）

			// 若一级内部节点未分配，则创建
			if (root_->ptrs[i1] == NULL) {
				Node* n = NewNode();
				if (n == NULL) return false;  // 分配失败
				root_->ptrs[i1] = n;
			}

			// 若二级节点（叶子节点）未分配，则创建
			if (root_->ptrs[i1]->ptrs[i2] == NULL) {
				Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));
				if (leaf == NULL) return false;  // 分配失败
				memset(leaf, 0, sizeof(*leaf));  // 初始化为空指针
				// 存储为Node*类型（内部节点的ptrs数组是Node*类型）
				root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);
			}

			// 优化：跳过当前叶子节点覆盖的所有key（批量处理）
			key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
		}
		return true;
	}
};